package com.data_structure_algorithm.algorithm;

/**
 * @Authror PABLO
 * @Date 2022/4/6 13:56
 * @Desc 递归拼接
 */
public class Splicing {


    //统计目标的字符个出现了几次


    //本次传入数组首元素和目标需要的字符匹配，看能满足多少，依次 --，
    // 如果本次传入的元素不需要在目标字符中出现，也--，得到一张记录表，
    //该表记录本次传入的元素和目标匹配的有效字符元素，返回给调用者
    //


    public static void main(String[] args) {
        String target = "abc";

        String[] arr = {"aaa", "bbb", "ccc"};

        int process = process(arr, target);
        System.out.println(process);
    }

    public static int process(String[] arr, String target) {
        System.out.println(target);
        if (target.length() == 0 || target == null) {
            return 0;
        }

        int min = Integer.MAX_VALUE;

        for (String item : arr
        ) {
            //返回当前字符不满足目标target的部分
            //不满足的部分说明数组中首元素没有，将不满足部分继续作为target，递归调用
            String minus = minus(target, item);
            if (minus.length() != target.length()) {
                min = Math.min(min, process(arr, minus));
            }
        }

        return min + (min == Integer.MAX_VALUE ? 0 : 1);

    }


    /**
     * @Description: 根据当前首元素，和target匹配
     * @Author: PABLO
     * @Date: 2022/4/6 14:06
     * @Params: [target 目标, first 数组中当前首元素]
     * @Return: java.lang.String 返回当前首元素不符合target的字符
     **/
    public static String minus(String target, String first) {
        char[] targetChars = target.toCharArray();

        char[] firstChars = first.toCharArray();

        //因为都是小写英文字母，范围26
        int[] count = new int[26];

        for (char item : targetChars) {
            //记录目标字符中某个字符出现的次数,如入参为abc,退出循环后，数组是[1,1,1,0,0,0,...]
            //item - 'a'的值相当于 26个英文子母对应的count下标，如a--0  b--1 c--2 ...z--25
            count[item - 'a']++;
        }
        //记录首元素字符中不符合target要求的字符
        //如first是aaa，那么count下标为0的要被--3次，只有 count的1,2下标（对应bc）,不受影响
        for (char item : firstChars) {
            //记录首元素字符集不符合的有哪些
            count[item - 'a']--;
        }

        //将该首元素符合的字符返回
        StringBuilder stringBuilder = new StringBuilder();

        for (int i = 0; i < count.length; i++) {
            //上面的--操作，会将target需要的并且该元素中存在的减去，返回不符合target元素的字符
            if (count[i] > 0) {
                for (int j = 0; j < count[i]; j++) {
                    stringBuilder.append((char) (i + 'a'));
                }
            }
        }

        return stringBuilder.toString();


    }

}
